class Solution
{
public:
    vector<int> findDiagonalOrder(vector<vector<int>> &mat)
    {
        int i = 0, j = 0;
        int m = mat.size();
        int n = mat[0].size();
        bool upDirectionFlag = true;
        vector<int> result;
        while (true)
        {
            result.push_back(mat[i][j]);
            if (i == m - 1 && j == n - 1)
            {
                break;
            }
            if ((i == 0 || j == n - 1) && upDirectionFlag)
            {
                upDirectionFlag = !upDirectionFlag;
                if (j == n - 1)
                {
                    ++i;
                }
                else
                {
                    ++j;
                }
            }
            else if ((j == 0 || i == m - 1) && !upDirectionFlag)
            {
                upDirectionFlag = !upDirectionFlag;
                if (i == m - 1)
                {
                    ++j;
                }
                else
                {
                    ++i;
                }
            }
            else
            {
                if (upDirectionFlag)
                {
                    ++j;
                    --i;
                }
                else
                {
                    ++i;
                    --j;
                }
            }
        }
        return result;
    }
};